// https://www.lintcode.com/problem/implement-queue-by-two-stacks/description?_from=ladder&&fromId=6

// class MyQueue {
// public:
//     stack<int> s1;
//     stack<int> s2;
//     MyQueue() {
//         // do intialization if necessary
//     }

//     /*
//      * @param element: An integer
//      * @return: nothing
//      */
//     void push(int element) {
//         while (!s2.empty())
//         {
//             int tmp = s2.top();
//             s2.pop();
//             s1.push(tmp);
//         }
//         s1.push(element);
//         while (!s1.empty())
//         {
//             int tmp = s1.top();
//             s1.pop();
//             s2.push(tmp);
//         }
//     }

//     /*
//      * @return: An integer
//      */
//     int pop() {
//       int tmp = s2.top();
//       s2.pop();
//       return tmp;
//     }

//     /*
//      * @return: An integer
//      */
//     int top() {
//         return s2.top();
//     }
// };


// 不用每次都倒空，stack1用来push，stack2用来pop，如果stack2还有，就不用把stack1里面的搬进来，空了再搬。
class MyQueue {
public:
    stack<int> s1;
    stack<int> s2;
    MyQueue() {
        // do intialization if necessary
    }

    /*
     * @param element: An integer
     * @return: nothing
     */
    void push(int element) {
        s1.push(element);
    }

    void adjust()
    {
        if (s2.empty())
        {
            while (!s1.empty())
            {
                s2.push(s1.top());
                s1.pop();
            }
        }
    }
    /*
     * @return: An integer
     */
    int pop() {
        adjust();
        int tmp = s2.top();
        s2.pop();
        return tmp;
    }

    /*
     * @return: An integer
     */
    int top() {
        adjust();
        return s2.top();
    }
};


// https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/submissions/
class CQueue {
public:
    stack<int> s1;
    stack<int> s2;
    CQueue() {
    }
    
    void appendTail(int value) {
        s1.push(value);
    }
    
    int deleteHead() {
        if (s2.empty()) {
            if (s1.empty()) return -1;
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }
        int tmp = s2.top();
        s2.pop();
        return tmp;
    }
};

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue* obj = new CQueue();
 * obj->appendTail(value);
 * int param_2 = obj->deleteHead();
 */